package com.zyk.grate_offer.class05;

import com.zyk.leetcode.TreeNode;

import java.util.Arrays;
import java.util.Stack;

/**
 * @author zhangsan
 * @date 2021/5/7 20:45
 */
public class Code01_ConstructBSTFromPreOrder {

    // 先序数组, 构建出搜索二叉树
    public static TreeNode bstFromPreorder(int[] nums) {
        if (nums == null || nums.length == 0) return null;
        return process(nums, 0, nums.length - 1);
    }

    public static TreeNode process(int[] nums, int L, int R) {
        if (L > R) return null;
        int firstBig = L + 1;
        for (; firstBig <= R; firstBig++) {
            if (nums[firstBig] > nums[L]) {
                break;
            }
        }
        TreeNode cur = new TreeNode(nums[L]);
        cur.left = process(nums, L + 1, firstBig - 1);
        cur.right = process(nums, firstBig, R);
        return cur;
    }

    // 2. 使用单调栈, 先算出每个大于当前位置的最左节点
    public static TreeNode bstFromPreorder2(int[] nums) {
        int N;
        if (nums == null || (N = nums.length) == 0)
            return null;
        int[] nearBig = new int[N];
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < N; i++) {
            while (!stack.isEmpty() && nums[stack.peek()] < nums[i]) {
                nearBig[stack.pop()] = i;
            }
            stack.push(i);
        }
        while (!stack.isEmpty()) {
            nearBig[stack.pop()] = -1;
        }
//        System.out.println(Arrays.toString(nearBig));
        return process2(nums, 0, nums.length - 1, nearBig);
    }

    public static TreeNode process2(int[] nums, int L, int R, int[] nearBig) {
        if (L > R) return null;
        int firstBig = nearBig[L] == -1 && nearBig[L] < R ? R + 1 : nearBig[L];
        TreeNode cur = new TreeNode(nums[L]);
        cur.left = process2(nums, L + 1, firstBig - 1, nearBig);
        cur.right = process2(nums, firstBig, R, nearBig);
        return cur;
    }

    // 2. 使用单调栈, 数组实现单调栈
    public static TreeNode bstFromPreorder3(int[] nums) {
        int N;
        if (nums == null || (N = nums.length) == 0)
            return null;
        int[] nearBig = new int[N];

        int size = 0;   // 数组实现栈结构
        int[] stack = new int[N];
        for (int i = 0; i < N; i++) {
            while (size > 0 && nums[stack[size-1]] < nums[i]) {
                nearBig[stack[--size]] = i;
            }
            stack[size++] = i;
        }
        while (size > 0) {
            nearBig[stack[--size]] = -1;
        }

        System.out.println(Arrays.toString(nearBig));
        return process2(nums, 0, nums.length - 1, nearBig);
    }

    public static TreeNode process3(int[] nums, int L, int R, int[] nearBig) {
        if (L > R) return null;
        int firstBig = nearBig[L] == -1 && nearBig[L] < R ? R + 1 : nearBig[L];
        TreeNode cur = new TreeNode(nums[L]);
        cur.left = process3(nums, L + 1, firstBig - 1, nearBig);
        cur.right = process3(nums, firstBig, R, nearBig);
        return cur;
    }

    public static void main(String[] args) {
        int[] pre = {8, 5, 1, 7, 10, 12};
//        int[] pre = {4, 2};
//        TreeNode root = bstFromPreorder(pre);
//        TreeNode root = bstFromPreorder2(pre);
        TreeNode root = bstFromPreorder3(pre);
        inPrint(root);
    }

    public static void inPrint(TreeNode root) {
        if (root == null) {
            return;
        }
        inPrint(root.left);
        System.out.println(root.val);
        inPrint(root.right);
    }

}
